class Solution {
public:
    unordered_map<int, char> ma;
    pair<int, bool> dp[15][2][2][2000];
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        ma[1] = digits[0][0];
        int temp = 1;
        for (int i = 1; i < digits.size(); i++)
        {
            temp *= 2;
            ma[temp] = digits[i][0];
        }
        return dfs(0, to_string(n), 0, 0, (1 << digits.size()) - 1);
    }
    int dfs(int pos, string s, int pre, int free, int t)
    {
        if (pos >= s.size()) return pre;
        if (dp[pos][pre][free][t].second) return dp[pos][pre][free][t].first;
        int ans = 0;
        if (!pre) ans += dfs(pos + 1, s, pre, 1, t);
        for (int i = t; i; i -= i & (-i))
        {
            int temp = i & (-i);
            if (free) ans += dfs(pos + 1, s, 1, free, t);
            else
            {
                if (ma[temp] > s[pos]) continue;
                else if (ma[temp] == s[pos]) ans += dfs(pos + 1, s, 1, 0, t);
                else ans += dfs(pos + 1, s, 1, 1, t);
            }
        }
        dp[pos][pre][free][t].second = 1;
        return dp[pos][pre][free][t].first = ans;
    }
};